package com.aurora.leetcode.answer;

public class LongestPublicPrefix_14 {
    /**14、最长公共前缀
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     * 如果不存在公共前缀，返回空字符串 ""。
     * */
    public static void main(String[] args) {
        String[] strs = {"aaa","aa","aaa"};
        System.out.println(longestCommonPrefix(strs));
    }

    /**我的解法一：
     * 假定第一个为最长公共前缀，找出公共前缀依次与后面的成员进行比较
     * @param strs
     * @return
     */
    public static String longestCommonPrefix(String[] strs) {
        String prefix = strs[0];
        if(strs.length == 0 || prefix.length() == 0) return "";
        int pos = prefix.length();//指定公共前缀长度
        int min;
        String current;
        for(int i=1; i<strs.length; ++i){
            current = strs[i];
            min = pos<current.length()?pos:current.length();
            int j = 0;
            for(j=0; j<min; ++j){
                if(current.charAt(j) != prefix.charAt(j)) break;
            }
            pos = j;
        }
        prefix = subString(prefix,pos-1);
//        prefix.substring(0,pos-1);
        return prefix;
    }
    public static String subString(String prefix, int pos){
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<=pos; ++i){
            sb.append(prefix.charAt(i));
        }
        return sb.toString();
    }


    /**解法二：纵向比较
     * 依次遍历相同位置的每一个字符串，如果此位置相同则继续下一个为止否则，保留此位置之前的字符串
     * 较容易，不做实现
     * */

    /**解法三： 分治
     * 将原字符串划分为两部分
     *       求出左边部分的公共前缀，
     *       求出右边部分的公共前缀，
     *          求左右的公共前缀
     * */
    public static String longestCommonPrefix2(String[] strs) {
        if(strs.length == 0 || strs[0].length() == 0) return "";
        else{
           return getPartialPrefix(strs,0,strs.length-1);
        }
    }
    public static String getPartialPrefix(String[] strs,int start, int end){
        if(strs.length == 1) return strs[0];
        else{
            int mid = (start+end)/2;
            String leftPrefix = getPartialPrefix(strs,0,mid);
            String rightPrefix = getPartialPrefix(strs,mid+1, end);
            return getCommonPrefix(leftPrefix,rightPrefix);
        }
    }

    public static String getCommonPrefix(String left, String right){
        int length = left.length()<right.length()?left.length():right.length();
        int i;
        for(i=0; i<length; ++i){
            if(left.charAt(i) != right.charAt(i)) break;
        }
        return left.substring(0,i-1);
    }
    /**解法四：分治
     * 显然，最长公共前缀的长度不会超过字符串数组中的最短字符串的长度。用
     * minLength表示字符串数组中的最短字符串的长度，则可以在 [0,minLength]的范围内通过二分查找得到最长公共前缀的长度。
     * 每次取查找范围的中间值mid，判断每个字符串的长度为mid的前缀是否相同，
     * 如果相同则最长公共前缀的长度一定大于或等于 mid，
     * 如果不相同则最长公共前缀的长度一定小于 mid，
     * 通过上述方式将查找范围缩小一半，直到得到最长公共前缀的长度。
     * */
    public String longestCommonPrefix3(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int minLength = Integer.MAX_VALUE;
        for (String str : strs) {
            minLength = Math.min(minLength, str.length());
        }
        int low = 0, high = minLength;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (isCommonPrefix(strs, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return strs[0].substring(0, low);
    }

    public boolean isCommonPrefix(String[] strs, int length) {
        String str0 = strs[0].substring(0, length);
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            String str = strs[i];
            for (int j = 0; j < length; j++) {
                if (str0.charAt(j) != str.charAt(j)) {
                    return false;
                }
            }
        }
        return true;
    }

}
